﻿#define _CRT_SECURE_NO_WARNINGS 1

//433. 最小基因变化
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {

        unordered_set<string> hash(bank.begin(), bank.end());//// 存储基因库里面的基因序列
        unordered_set<string> vis; // ⽤来标记已经搜索过的状态
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);
        int step = 0;
        string change = "ACGT";
        while (q.size())
        {
            step++;
            int n = q.size();
            while (n--)
            {
                string t = q.front();
                q.pop();
                for (int i = 0; i < 8; ++i)
                {
                    string tmp = t;//细节问题,我们只是修改字符串的一个字符,下一次还想在原始字符串中修改下一个字符
                    for (int j = 0; j < 4; ++j)
                    {
                        tmp[i] = change[j];
                        if (hash.count(tmp) && !vis.count(tmp))
                        {
                            if (tmp == endGene) return step;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }

        }
        return -1;
    }
};